# from collections import  deque
# d = deque()
# d.append(3)
# print(len(d))
# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
from collections import deque
class Solution:
    def levelOrder(self, root: TreeNode):
        res = []
        if root == None:
            return res
        d = deque()
        d.append(root)
        while len(d):
            Node = d.popleft()
            res.append(Node.val)
            if Node.left != None:
                d.append(Node.left)
            if Node.right != None:
                d.append(Node.right)
        return res

class Solutionhh:
    def levelOrder(self, root: TreeNode):
        import collections,copy
        height = 0
        d = collections.deque()
        res = []
        re = True
        if root==None:
            return None
        d.append(root)
        while len(d):
            levellist = []
            levelnodenums = len(d)
            if height%2==0:
                for _ in range(levelnodenums):
                    levellist.append(d.popleft())
            else:
                for _ in range(levelnodenums):
                    levellist.append(d.pop())
                re = False
            kk = copy.deepcopy(levellist)
            res.append(kk)
            if re:
                for i in levellist:
                    if i.left!=None:
                        d.append(i.left)
                    if i.right!=None:
                         d.append(i.right)
            else:
                for i in levellist[::-1]:
                    if i.left!=None:
                        d.append(i.left)
                    if i.right!=None:
                         d.append(i.right)
            re = True
            height+=1
        return res

if __name__ == '__main__':
    l = [3, 9, 20, 15, 7]
    root = TreeNode(3)
    root.left = TreeNode(9)
    root.right = TreeNode(20)
    root.right.left = TreeNode(15)
    root.right.right = TreeNode(7)
    s = Solutionhh()
    re =s.levelOrder(root)
    for x in re:
        for i in x:
            print(i.val,end=" ")
        print()
